/**
 * Floyed 算法
*/

#include "MGraph.c"

#ifndef MGRAPH_FLOYED
#define MGRAPH_FLOYED
int floyed(MGraph* g, WeightType **d, int **path) {
    // 初始化
    for (int i=0; i<g->vertexNum; i++) {
        for (int j=0; j<g->vertexNum; j++) {
            d[i][j] = g->g[i][j];
            path[i][j] = Connectionless;
        }
    }
    for (int k=0; k<g->vertexNum; k++) {
        for (int i=0; i<g->vertexNum; i++) {
            for (int j=0; j<g->vertexNum; j++) {
                if (d[i][k] + d[k][j] < d[i][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    if (i==j && d[i][j]<0) {
                        // 发现负值圈
                        return 0;
                    }
                    path[i][j] = k;
                }
            }
        }
    }
    return 1;
}

#endif
